/*********************************************************
   Copyright: (C) 2008-2010 by Steven Schveighoffer.
              All rights reserved

   License: Boost Software License version 1.0

   Permission is hereby granted, free of charge, to any person or organization
   obtaining a copy of the software and accompanying documentation covered by
   this license (the "Software") to use, reproduce, display, distribute,
   execute, and transmit the Software, and to prepare derivative works of the
   Software, and to permit third-parties to whom the Software is furnished to
   do so, all subject to the following:

   The copyright notices in the Software and this entire statement, including
   the above license grant, this restriction and the following disclaimer, must
   be included in all copies of the Software, in whole or in part, and all
   derivative works of the Software, unless such copies or derivative works are
   solely in the form of machine-executable object code generated by a source
   language processor.

   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
   SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
   FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
   ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
   DEALINGS IN THE SOFTWARE.

**********************************************************/

module dcollections.ArrayList;
public import dcollections.model.List,
       dcollections.model.Keyed,
       std.array; // needed for range functions on arrays.
private import dcollections.DefaultFunctions;

version(unittest) private import std.traits;

/***
 * This class is a wrapper around an array which provides the necessary
 * implemenation to implement the List interface
 *
 * Adding or removing any element invalidates all cursors.
 *
 * This class serves as the gateway between builtin arrays and dcollection
 * classes.  You can construct an ArrayList with a builtin array serving as
 * the storage, and you can access the ArrayList as an array by slicing the
 * collection (as in alist[]).  Neither of these make copies of the array, so
 * you can continue to use the array in both forms.
 */
final class ArrayList(V) : Keyed!(size_t, V), List!(V) 
{
    version(unittest)
        private enum doUnittest = isIntegral!V;
    else
        private enum doUnittest = false;

    private V[] _array;

    /**
     * The array cursor gives a reference to an element in the array.
     *
     * All operations on the cursor are O(1)
     */
    struct cursor
    {
        private V *ptr;
        private bool _empty = false;
        
        /**
         * get the value pointed to
         */
        @property inout(V) front() inout
        {
            assert(!_empty, "Attempting to read the value of an empty cursor of " ~ ArrayList.stringof);
            return *ptr;
        }

        /**
         * set the value pointed to
         */
        @property V front(V v)
        {
            assert(!_empty, "Attempting to write the value of an empty cursor of " ~ ArrayList.stringof);
            return (*ptr = v);
        }

        /**
         * pop the front of the cursor.  This only is valid if the cursor is
         * not empty.  Normally you do not use this, but it allows the cursor
         * to be considered a range, convenient for passing to range-accepting
         * functions.
         */
        void popFront()
        {
            assert(!_empty, "Attempting to popFront() an empty cursor of " ~ ArrayList.stringof);
            ptr++;
            _empty = true;
        }

        /**
         * returns true if this cursor does not point to a valid element.
         */
        @property bool empty() const
        {
            return _empty;
        }

        /**
         * Length is trivial to add, allows cursors to be used in more
         * algorithms.
         */
        @property size_t length() const
        {
            return _empty ? 0 : 1;
        }

        /**
         * opIndex costs nothing, and it allows more algorithms to accept
         * cursors.
         */
        inout(V) opIndex(size_t idx) inout
        {
            assert(idx < length, "Attempt to access invalid index on cursor");
            return *ptr;
        }

        /**
         * Save property needed to satisfy forwardRange requirements.
         */
        @property inout(cursor) save() inout
        {
            return this;
        }

        /**
         * compare two cursors for equality.  Note that only the position of
         * the cursor is checked, whether it's empty or not is not checked.
         */
        bool opEquals(ref const(cursor) it) const
        {
            return it.ptr is ptr;
        }
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList(1, 2, 3, 4, 5);
        auto cu = al.elemAt(2);
        assert(!cu.empty);
        assert(cu.front == 3);
        assert((cu.front = 8)  == 8);
        assert(cu.front  == 8);
        assert(al == cast(V[])[1, 2, 8, 4, 5]);
        cu.popFront();
        assert(cu.empty);
        assert(al == cast(V[])[1, 2, 8, 4, 5]);
    }


    /**
     * An array list range is a D builtin array.  Using the builtin array
     * allows for all possible array functions already present in the library.
     */
    alias V[] range;

    /**
     * Create an array list based on a number of elements.
     */
    this(V[] elems...)
    {
        _array = elems.dup;
    }

    /**
     * Use an array as the backing storage.  This does not duplicate the
     * array.  Use new ArrayList(storage.dup) to make a distinct copy.  Beware
     * of using a stack-based array when using this constructor!
     */
    this(V[] storage)
    {
        _array = storage;
    }

    /**
     * Constructor that uses the given iterator to get the initial elements.
     */
    this(Iterator!V initialElements)
    {
        add(initialElements);
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList(1, 2, 3, 4, 5);
        auto al2 = new ArrayList(al);
        assert(al == al2);
        al[0] = 2;
        assert(al != al2);
    }

    /**
     * clear the container of all values.  Note that unlike arrays, it is no
     * longer safe to use cursors/elements that were in the array list.  This
     * is consistent with the other container types.
     */
    ArrayList clear()
    {
        _array.length = 0;
        _array.assumeSafeAppend();
        return this;
    }

    /**
     * return the number of elements in the collection
     */
    @property size_t length() const
    {
        return _array.length;
    }

    /**
     * return a cursor that points to the first element in the list.
     */
    @property inout(cursor) begin() inout
    {
        return _array.begin;
    }

    /**
     * return a cursor that points to just beyond the last element in the
     * list.  The cursor will be empty, so you cannot call front on it.
     */
    @property inout(cursor) end() inout
    {
        return _array.end;
    }

    private int _apply(scope int delegate(ref bool, ref size_t, ref V) dg, range r)
    {
        int dgret;
        auto i = r.ptr;
        auto last = r.ptr + r.length;
        auto endref = end.ptr;

        bool doRemove = false;

        //
        // loop before removal
        //
        for(; dgret == 0 && i != last; i++)
        {
            doRemove = false;
            size_t key = i - _array.ptr;
            if((dgret = dg(doRemove, key, *i)) == 0)
            {
                if(doRemove)
                {
                    //
                    // first removal
                    //
                    i++;
                    break;
                }
            }
        }

        //
        // loop after first removal
        //
        if(doRemove)
        {
            auto nextGood = i-1;
            for(; i < endref; i++, nextGood++)
            {
                doRemove = false;
                size_t key = i - _array.ptr;
                if(i >= last || dgret != 0 || (dgret = dg(doRemove, key, *i)) != 0 || !doRemove)
                {
                    //
                    // either not calling dg any more or doRemove was
                    // false.
                    //
                    *nextGood = *i;
                }
                else
                {
                    //
                    // dg requested a removal
                    //
                    nextGood--;
                }
            }

            //
            // shorten the length
            //
            _array = _array.ptr[0..nextGood - _array.ptr];
            _array.assumeSafeAppend();
        }
        return dgret;
    }

    private int _apply(scope int delegate(ref bool, ref V) dg, range r)
    {
        int _dg(ref bool b, ref size_t k, ref V v)
        {
            return dg(b, v);
        }
        return _apply(&_dg, r);
    }

    /**
     * Iterate over the elements in the ArrayList, telling it which ones
     * should be removed
     *
     * Use like this:
     *
     * -------------
     * // remove all odd elements
     * foreach(ref doRemove, v; &arrayList.purge)
     * {
     *   doRemove = (v & 1) != 0;
     * }
     * ------------
     */
    int purge(scope int delegate(ref bool doRemove, ref V value) dg)
    {
        return _apply(dg, _array);
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[0, 1, 2, 3, 4]);
        foreach(ref p, i; &al.purge)
        {
            p = (i & 1);
        }

        assert(al == cast(V[])[0, 2, 4]);
    }

    /**
     * Iterate over the keys and elements in the ArrayList, telling it which
     * ones should be removed.
     *
     * Use like this:
     * -------------
     * // remove all odd indexes
     * foreach(ref doRemove, k, v; &arrayList.purge)
     * {
     *   doRemove = (k & 1) != 0;
     * }
     * ------------
     */
    int keypurge(scope int delegate(ref bool doRemove, ref size_t key, ref V value) dg)
    {
        return _apply(dg, _array);
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        foreach(ref p, k, i; &al.keypurge)
        {
            p = (k & 1);
        }

        assert(al == cast(V[])[1, 3, 5]);
    }

    /**
     * remove all the elements in the given range.  Returns a valid cursor that
     * points to the element just beyond the given range
     *
     * Runs in O(n) time.
     */
    cursor remove(range r)
    in
    {
        assert(r.ptr >= _array.ptr);
        assert(r.ptr + r.length <= _array.ptr + _array.length);
    }
    body
    {
        int check(ref bool b, ref V)
        {
            b = true;
            return 0;
        }
        _apply(&check, r);
        return cursor(r.ptr);
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        al.remove(al[2..4]);
        assert(al == cast(V[])[1, 2, 5]);
    }

    /**
     * remove the element pointed to by elem.  Returns a cursor to the element
     * just beyond this one.
     *
     * Runs in O(n) time
     */
    cursor remove(cursor elem)
    {
        if(elem.empty)
            // nothing to remove, but we should get the next element.
            return cursor(elem.ptr);
        return remove(elem.ptr[0..1]);
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        al.remove(al.elemAt(2));
        assert(al == cast(V[])[1, 2, 4, 5]);
    }

    /**
     * get a cursor at the given index
     */
    inout(cursor) elemAt(size_t idx) inout
    in
    {
        assert(idx < _array.length);
    }
    body
    {
        return inout(cursor)(_array.ptr + idx);
    }

    /**
     * get the value at the given index.
     */
    inout(V) opIndex(const(size_t) key) inout
    {
        return _array[key];
    }

    /**
     * set the value at the given index.
     */
    V opIndexAssign(V value, size_t key)
    {
        return _array[key] = value;
    }

    /**
     * set the value at the given index
     */
    ArrayList set(size_t key, V value)
    {
        this[key] = value;
        return this;
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        assert(al.set(2, 8)[2] == 8);
        assert(al.set(3, 10)[3] == 10);
        assert(al == cast(V[])[1, 2, 8, 10, 5]);
    }

    /**
     * iterate over the collection
     */
    int opApply(scope int delegate(ref V value) dg)
    {
        int retval;
        foreach(ref v; _array)
        {
            if((retval = dg(v)) != 0)
                break;
        }
        return retval;
    }

    /**
     * iterate over the collection with key and value
     */
    int opApply(scope int delegate(ref size_t key, ref V value) dg)
    {
        int retval = 0;
        foreach(i, ref v; _array)
        {
            if((retval = dg(i, v)) != 0)
                break;
        }
        return retval;
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        size_t idx = 0;
        foreach(i; al)
        {
            assert(i == al[idx++]);
        }
        assert(idx == al.length);
        idx = 0;
        foreach(k, i; al)
        {
            assert(idx == k);
            assert(i == idx + 1);
            assert(i == al[idx++]);
        }
        assert(idx == al.length);
    }

    /**
     * returns true if the given index is valid
     *
     * Runs in O(1) time
     */
    bool containsKey(const(size_t) key) const
    {
        return key < length;
    }

    /**
     * adds all elements from the given iterator to the end of the list.
     */
    ArrayList add(Iterator!(V) coll)
    {
        if(auto al = cast(ArrayList)coll)
        {
            //
            // optimized case
            //
            return add(al._array);
        }

        //
        // generic case
        //
        auto numAdded = coll.length;
        if(numAdded != NO_LENGTH_SUPPORT)
        {
            if(numAdded > 0)
            {
                auto i = _array.length;
                _array.length += numAdded;
                foreach(v; coll)
                    _array [i++] = v;
            }
        }
        else
        {
            foreach(v; coll)
                _array ~= v;
        }
        return this;
    }


    /**
     * appends the elems to the end of the list
     */
    ArrayList add(V[] elems...)
    {
        if(elems.length)
            _array ~= elems;
        return this;
    }

    static if(doUnittest) unittest
    {
        // add single element
        bool wasAdded = false;
        auto al = new ArrayList;
        al.add(1).add(2);
        assert(al.length == 2);
        assert(al == cast(V[])[1, 2]);

        // add other collection
        al.add(al);
        al.add(al);
        assert(al == cast(V[])[1, 2, 1, 2, 1, 2, 1, 2]);

        // add array
        al.clear();
        al.add(cast(V[])[1, 2, 3, 4, 5]).add(1,2,3,4,5);
        assert(al == cast(V[])[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]);
    }


    /**
     * returns a concatenation of the array list and another list.
     */
    ArrayList concat(List!(V) rhs)
    {
        return dup().add(rhs);
    }

    /**
     * returns a concatenation of the array list and an array.
     */
    ArrayList concat(V[] array)
    {
        return new ArrayList(_array ~ array);
    }

    /**
     * returns a concatenation of the array list and an array.
     */
    ArrayList concat_r(V[] array)
    {
        return new ArrayList(array ~ _array);
    }

    version(testcompiler)
    {
    }
    else
    {
        // workaround for compiler deficiencies
        alias concat opCat;
        alias concat_r opCat_r;
        alias add opCatAssign;
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        auto al2 = al.concat(al);
        assert(al2 !is al);
        assert(al2 == cast(V[])[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]);
        assert(al == cast(V[])[1, 2, 3, 4, 5]);

        al2 = al.concat(cast(V[])[6, 7, 8, 9, 10]);
        assert(al2 !is al);
        assert(al2 == cast(V[])[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
        assert(al == cast(V[])[1, 2, 3, 4, 5]);

        al2 = al.concat_r(cast(V[])[6, 7, 8, 9, 10]);
        assert(al2 !is al);
        assert(al2 == cast(V[])[6, 7, 8, 9, 10, 1, 2, 3, 4, 5]);
        assert(al == cast(V[])[1, 2, 3, 4, 5]);

        al2 = al ~ al;
        assert(al2 !is al);
        assert(al2 == cast(V[])[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]);
        assert(al == cast(V[])[1, 2, 3, 4, 5]);

        al2 = al ~ cast(V[])[6, 7, 8, 9, 10];
        assert(al2 !is al);
        assert(al2 == cast(V[])[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
        assert(al == cast(V[])[1, 2, 3, 4, 5]);

        al2 = cast(V[])[6, 7, 8, 9, 10] ~ al;
        assert(al2 !is al);
        assert(al2 == cast(V[])[6, 7, 8, 9, 10, 1, 2, 3, 4, 5]);
        assert(al == cast(V[])[1, 2, 3, 4, 5]);
    }

    /**
     * Returns a slice of an array list.
     *
     * The returned slice begins at index b and ends at, but does not include,
     * index e.
     */
    inout(range) opSlice(size_t b, size_t e) inout
    {
        return _array[b..e];
    }

    /**
     * Slice an array given the cursors
     */
    inout(range) opSlice(inout(cursor) b, inout(cursor) e) inout
    {
        if(e.ptr >= b.ptr && e.ptr <= end.ptr && b.ptr >= begin.ptr)
            return b.ptr[0..(e.ptr-b.ptr)];
        throw new Exception("invalid slice parameters to " ~ ArrayList.stringof);
    }

    /**
     * get the array that this array represents.  This is NOT a copy of the
     * data, so modifying elements of this array will modify elements of the
     * original ArrayList.  Appending elements from this array will not affect
     * the original array list just like appending to an array will not affect
     * the original.
     */
    inout(range) opSlice() inout
    {
        return _array;
    }

    /**
     * Returns a copy of an array list
     */
    ArrayList dup()
    {
        return new ArrayList(_array.dup);
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(1);
        al.add(2);
        auto al2 = al.dup;
        assert(al._array !is al2._array);
        assert(al == al2);
        al[0] = 0;
        al.add(3);
        assert(al2 == cast(V[])[1, 2]);
        assert(al == cast(V[])[0, 2, 3]);
    }

    /**
     * operator to compare two objects.
     *
     * If o is a List!(V), then this does a list compare.
     * If o is null or not an ArrayList, then the return value is 0.
     */
    override bool opEquals(Object o)
    {
        if(o !is null)
        {
            auto li = cast(List!(V))o;
            if(li !is null && li.length == length)
            {
                if(auto al = cast(ArrayList)o)
                    return this == al._array;
                else
                {
                    size_t i = 0;
                    foreach(elem; li)
                    {
                        // NOTE this is a workaround for compiler bug 4088
                        static if(is(V == interface))
                        {
                            if(cast(Object)elem != cast(Object)_array[i++])
                                return false;
                        }
                        else
                        {
                            if(elem != _array[i++])
                                return false;
                        }
                    }

                    //
                    // equal
                    //
                    return true;
                }
            }
        }
        //
        // no comparison possible.
        //
        return false;
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        assert(al == al.dup);
    }

    /**
     * Compare to a V array.
     *
     * equivalent to this[] == array.
     */
    bool opEquals(V[] array)
    {
        // this is to work around compiler bug 4088 and 4589
        static if(is(V == interface))
        {
            return std.algorithm.equal!"cast(Object)a == cast(Object)b"(this[], array);
        }
        else
        {
            return _array == array;
        }
    }

    /**
     *  Look at the element at the front of the ArrayList.
     */
    @property inout(V) front() inout
    {
        return _array[0];
    }

    /**
     * Look at the element at the end of the ArrayList.
     */
    @property inout(V) back() inout
    {
        return _array[$-1];
    }

    /**
     * Remove the element at the end of the ArrayList and return its value.
     */
    V take()
    {
        auto retval = _array[$-1];
        _array = _array[0..$-1];
        _array.assumeSafeAppend();
        return retval;
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        assert(al.take() == 5);
        assert(al == cast(V[])[1, 2, 3, 4]);
    }

    /**
     * Get the index of a particular cursor.
     */
    size_t indexOf(const(cursor) c) const
    {
        assert(belongs(c));
        return c.ptr - begin.ptr;
    }

    /**
     * returns true if the given cursor belongs points to an element that is
     * part of the container.  If the cursor is the same as the end cursor,
     * true is also returned.
     */
    bool belongs(const(cursor) c) const
    {
        auto last = end;
        if(c.ptr == last.ptr && !c.empty)
            // a non-empty cursor which points past the array 
            return false;
        return c.ptr >= _array.ptr && c.ptr <= last.ptr;
    }

    bool belongs(const(range) r) const
    {
        return(r.ptr >= _array.ptr && r.ptr + r.length <= _array.ptr + _array.length);
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 2, 3, 4, 5]);
        auto cu = al.elemAt(2);
        assert(cu.front == 3);
        assert(al.belongs(cu));
        assert(al.indexOf(cu) == 2);
        auto r = al[0..2];
        assert(al.belongs(r));
        assert(al.indexOf(r.end) == 2);

        auto al2 = al.dup;
        assert(!al2.belongs(cu));
        assert(!al2.belongs(r));
    }

    /**
     * Sort according to a given comparison function
     */
    ArrayList sort(scope bool delegate(ref V v1, ref V v2) comp)
    {
        std.algorithm.sort!(comp)(_array);
        return this;
    }

    /**
     * Sort according to a given comparison function
     */
    ArrayList sort(bool function(ref V v1, ref V v2) comp)
    {
        std.algorithm.sort!(comp)(_array);
        return this;
    }

    /**
     * Sort according to the default comparison routine for V
     */
    ArrayList sort()
    {
        std.algorithm.sort!(DefaultLess!(V))(_array);
        return this;
    }

    /**
     * Sort the list according to the given compare functor.  This is
     * a templatized version, and so can be used with functors, and might be
     * inlined.
     *
     * TODO: this should be called sort
     * TODO: if bug 3051 is resolved, then this can probably be
     * sortX(alias less)()
     * instead.
     */
    ArrayList sortX(T)(T less)
    {
        std.algorithm.sort!less(_array);
        return this;
    }

    static if(doUnittest) unittest
    {
        auto al = new ArrayList;
        al.add(cast(V[])[1, 3, 5, 6, 4, 2]);
        al.sort();
        assert(al == cast(V[])[1, 2, 3, 4, 5, 6]);
        al.sort(delegate bool (ref V a, ref V b) { return b < a; });
        assert(al == cast(V[])[6, 5, 4, 3, 2, 1]);
        al.sort(function bool (ref V a, ref V b) { if((a ^ b) & 1) return cast(bool)(a & 1); return a < b; });
        assert(al == cast(V[])[1, 3, 5, 2, 4, 6]);

        struct X
        {
            V pivot;
            // if a and b are on both sides of pivot, sort normally, otherwise,
            // values >= pivot are treated less than values < pivot.
            bool opCall(V a, V b)
            {
                if(a < pivot)
                {
                    if(b < pivot)
                    {
                        return a < b;
                    }
                    return false;
                }
                else if(b >= pivot)
                {
                    return a < b;
                }
                return true;
            }
        }

        X x;
        x.pivot = 4;
        al.sortX(x);
        assert(al == cast(V[])[4, 5, 6, 1, 2, 3]);
    }
}

// some extra functions needed to support range functions guaranteed by dcollections.

/**
 * Get the begin cursor of an ArrayList range.
 */
@property inout(ArrayList!(T).cursor) begin(T)(inout(T[]) r)
{
    return inout(ArrayList!(T).cursor)(r.ptr, r.empty);
}

/**
 * Get the end cursor of an ArrayList range.
 */
@property inout(ArrayList!T.cursor) end(T)(inout(T[]) r)
{
    return inout(ArrayList!(T).cursor)(r.ptr + r.length, true);
}

unittest
{
    // declare the array list types that should be unit tested.
    ArrayList!ubyte  al1;
    ArrayList!byte   al2;
    ArrayList!ushort al3;
    ArrayList!short  al4;
    ArrayList!uint   al5;
    ArrayList!int    al6;
    ArrayList!ulong  al7;
    ArrayList!long   al8;

    // ensure that reference types can be used
    ArrayList!(uint*) al9;
    interface I {}
    class C : I {}
    ArrayList!C al10;
    ArrayList!I al11; // fails with 2.050
}
